This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (5)

-1
votes
1answer
62 views

Show that [0,1) is equinumerous to (0,1] by giving an example of a bijection from [0,1) to (0,1] [closed]

Just trying to do my math homework. Need some help. "Show that [0,1) is equinumerous to (0,1] by giving an example of a bijection from [0,1) to (0,1]"
0
votes
2answers
23 views

Partitioning graph edges into two cycleless sets

Given a directed graph $G=\left(V,E\right)$, provide an algorithm that partitions $E$ into two disjoints sets $E_1,E_2$ such that $E=E_1\cup E_2$ and $G(V,E_1)$, $G(V,E_2)$ have no cycles. The ...
1
vote
2answers
17 views

Probability that the numbers on the tags marked $ 1; 2;…; n$ will be consecutive integers.

A random box contains tags marked $ 1; 2;...; n$. Two tags are chosen at random with replacement. Find the probability that the numbers on the tags will be consecutive integers. My Attempt Case I: ...
2
votes
1answer
30 views

Remainder of a combination

Problem from a contest: What is the remainder when $\binom{169}{13}$ is divided by $13^5$? I thought that Wolstenholme's/Babbage's would help, but not entirely sure how.
1
vote
1answer
49 views

Problem on Möbius function on a finite poset

I try to solve excercise 3.129 in Stanleys Enumerative combinatorics vol 1. The problem is the following: Let $P$ be a finite poset, and let $\mu$ be the Möbius function of $P \cup \{ ...
0
votes
1answer
19 views

hi, for an independent event, like flipping a fair coin does Pr(A|B) always equal to Pr(B|A)?

for an independent event, like flipping a fair coin does Pr(A|B) = Pr(B|A)? Example You flip a fair coin, independently, three times, Event A. The first flip results in heads Event B. The coin ...
3
votes
2answers
43 views

Silly mistake on evaluating the sixth term of $\left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$?

I am trying to evaluate the sixth term of $\displaystyle \left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$ with the binomial theorem. I've done the following: The sixth term might be the term for $k=5$ ...
1
vote
1answer
34 views

Two Urns contain white and black balls, drawn using a set of rules. Probability that nth ball drawn is white.

Two urns contain respectively 'a white and b black' and 'b white and a black' balls. A series of drawings is made according to the following rules: (i) Each time only ball is drawn and immediately ...
0
votes
2answers
52 views

Any 3 letters shuffled in a word- What is the probability that the word remains the same? [closed]

A sign reads "ARKANSAS". Three letters are removed and put back into the three empty space at random. What is the Probability the sign still reads "ARKANSAS"?
3
votes
0answers
56 views

Can this summation be expressed differently?

Lets say I have a sum that states the following $$ \sum_{j=0}^{k-c} {k-c \choose j}\ln(a)^{k-c-j} \frac{d^j}{dx^j}[(x)_c] $$ where $(x)_c$ is the falling factorial such that $$ (x)_c = ...
0
votes
0answers
47 views

linear extension of a finite poset

I am trying to solve exc 3.57 in Stanley's Enumerative combinatorics vol 1. The problem is to show that the number $e(P)$ of linear extensions of a finite poset $P$ satisfies $$e(P) \geq ...
3
votes
2answers
37 views

Graph theory - inequality

I'm having troubles solving the following problem which is about proving an inequality in the field of graph theory. We consider G = (V,E) a graph with n a natural ...
2
votes
1answer
18 views

How many possible permutations are possible if ranking n entities using the 'standard competition ranking' strategy?

I don't know if I'm missing something here, but this doesn't look as straightforward to me as I thought it to be. I basically want to calculate the number of unique rankings that are possible when ...
4
votes
2answers
47 views

A sequence $a_i$ such that $|a_1-a_2|,|a_2-a_3|,\ldots$ is also permutation of the positive integers

Let $a_1,a_2,\ldots,$ be a permutation of the positive integers. Is it possible that $|a_1-a_2|,|a_2-a_3|,\ldots$ is also a permutation of the positive integer? My idea is to construct the sequence ...
1
vote
1answer
23 views

Need help in understanding how to solve combinatorial problem involving difference between values

So here is the problem from the book: Y represents the difference between the number of heads and tails from a coin that was tossed k times. We want to know all possible values of Y. Then, say k = ...
-2
votes
0answers
9 views

Why doesnt a (43, 43, 7, 7, 1)-design exist according to the conditions?

I have tested this using the necessary conditions for a BIBD and it's giving me a green light but I know this isn't a design. Why not?
1
vote
0answers
21 views

How many pure trees with a fixed number of nodes exist?

How many pure trees of size (number of nodes) $n$ exist? Apart from having this fixed size, the trees can be arbitrary. The sequence starts like this: Here's the beginning of the sequence:
2
votes
2answers
52 views

Why isn't Mary a victim of the permutation?

I've answered the following question: In a class, there are 8 female students in which one of them is called Mary and seven male students, in which one of them is called John. Considering ...
6
votes
2answers
138 views

What is the coefficient of $x^{25}$ in $(x^3 + x + 1)^{10}$?

Working on some contest problems and came across this question. Here's what I have so far on the off chance that my thinking is correct... So using Vieta's the coefficient of the $x^{25}$ should be ...
0
votes
1answer
30 views

Orthogonal Latin Square

Find a Latin square orthogonal to the following Latin square: 0 2 1 3 2 0 3 1 3 1 2 0 1 3 0 2 I have done this by using trial and error. But my ...
1
vote
1answer
11 views

Given the points $A,B,C,D$ in a straight line $m$ and $A,E,F,G$ in a straight line $n$, how many triangles can be formed with these points?

Given the points $A,B,C,D$ in a line $m$ and $A,E,F,G$ in a straight line $n$, how many triangles can be formed with these points? I've done the following: I've used the following heuristic: ...
3
votes
1answer
105 views

Number of self-avoiding rook walks in a rectangular grid

I was wondering how many self-avoiding rook walks there are on an $m×n$ grid. A self-avoiding rook walk is a path from the bottom left corner to the top right corner of the grid, composed only of ...
2
votes
0answers
24 views

Identifying a function that involves combinations of terms

I need to know if a function exists that partitions terms in such a way as seen below $$ \frac{d^n}{dx^n}[\frac{(x)_c}{n!}] $$ Note that $(x)_c$ is the falling factorial of x and $c \geq n$, This in ...
3
votes
0answers
53 views

The number of partitions by distinct positive numbers

Let $N>0$ be a natural number and let $P(N)$ denote the number of ways to write $N$ as a finite sum of $a_i$ such that the $a_i$ are strictly decreasing positive natural numbers. There is a paper ...
1
vote
3answers
52 views

Combinatorial card game [duplicate]

There is a card game I've played before, where it goes as follows: You take a standard deck of cards, and shuffle them randomly. You then proceed by flipping each card and placing them down, ...
1
vote
0answers
27 views

Number of non-crossing pairs

Let $n,k$ be positive integers. What is the number of sets of $k$ distinct ordered pairs $\{(a_1,b_1),\ldots,(a_k,b_k)\}$ such that $1\leq a_i,b_i\leq n$ are integers, and for no $i\neq j$ is it the ...
0
votes
0answers
48 views

Recurrence of a trapped random walk

i am wondering how behaves a symmetric random walk on $\mathbb Z$ except in $\pm 1$ where it goes towards 0 with probability $p$ and towards $\pm 2$ with probability $ q < p \ (p+q=1)$ ? on which ...
0
votes
1answer
42 views

Order dice rolls in the game of Risk

Last evening I was playing the game of Risk with some friends, and this question came to my mind: Can one order all the possible dice rolls of the attacker (from the best one to the worst one) ...
7
votes
2answers
60 views

Sum of cells on infinite board is even

Let $a,b,c$ be pairwise relatively prime positive integers. In an infinite checker board (infinite in all directions), each cell contains an integer. The sum of the integers in any $a\times a$ square ...
0
votes
1answer
42 views

How do you load $n$ cannisters into $m$ trucks such that no truck is overloaded

We have $n$ cannisters, and for each one there is a specified subset of trucks which can carry it. There are $m$ trucks that can each hold $k$ cannisters. Is there a way to load all $n$ cannisters ...
1
vote
1answer
24 views

Number of ways to place chess figures on one line of chess board [duplicate]

How many ways to place chess figures of one color (2 rooks, 2 knights, 2 bishops, 1 king and 1 queen) on one line of chess board such that 2 bishops are located on the cells with different color and ...
2
votes
4answers
38 views

Consider the number of $3$ distinct numbers formed with the digits $2,3,5,8,9$. How many of them are even?

I'm trying to answer the following: Consider the number of $3$ distinct numbers formed with the digits $2,3,5,8,9$. How many of them are even? I first tried to make the following counting: First ...
4
votes
3answers
89 views

Using up letters on a refrigerator is NP-complete

You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are ...
0
votes
0answers
26 views

Possible choices for coloring boxes with exactly n colors

I have a number of boxes $N$ that I each need to paint with one color chosen from $n$ available colors. Every color must be used at least once and the order in which I color the boxes matters. For ...
1
vote
1answer
44 views

Is this combinatorial problem for noncommutative variables known?

Suppose that I have two non-commutative variables $a,b$. Then the number of different strings given by $(a+b)^n$ is $2^n$ and their lenght is $n$. Let me choose $n=5$. I can write $$ ...
6
votes
3answers
95 views

what's the summation of this finite sequence?

$a$ and $b$ are positive integers. The summation is $$\sum\limits_{x = 1}^a {x\left( {\begin{array}{*{20}{c}} {a + b - x}\\ b \end{array}} \right)} .$$ Any closed-form expression? I thought it ...
2
votes
0answers
42 views

Some four clubs have exactly $1$ student in common

There are $100$ students in a school, and they form $450$ clubs. Any two clubs have at least $3$ students in common, and any five clubs have no more than $1$ student in common. Must it be that some ...
0
votes
1answer
27 views

combinatorics four digits out of three

With three given digits (1,2,3), how many unique four-digit combinations can be made if all three digits must be present but may be repeated? Example of correct combinations: (1,2,3,3) (1,1,2,3) ...
2
votes
1answer
74 views

Number of ways to select non-adjacent squares from a rectangular grid?

I know that the number of selections of $k$ non-adjacent objects from $n$ objects (in a line) is ${n-k+1 \choose k}$, and for all possible values of $k$ including 0, it's $F_n$, the $n^{th}$ Fibonacci ...
1
vote
0answers
29 views

A problem related to inclusion-exclusion principle

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. For example,N=10 and the positive integers are ...
1
vote
0answers
13 views

How to find the configuration of a rigid system that minimizes the distance of the end points in a closed loop

I am trying to find a more elegant way to solve this problem as setting it as an optimization problem. Currently, I have 5 different types of elbow joints 1- 30 degrees 2- 50 degrees 3- 60 degrees ...
0
votes
2answers
45 views

Birthday Paradox: why permutations and not combinations?

The Birthday Problem: given $n$ people (typically $n<365$), what is the probability that some pair of them share a birthday (omitting Feb 29th, for simplicity)? The solution: First, find the ...
0
votes
0answers
11 views

Name for a generalization of Dyck paths, Motzkin paths

A Dyck path is a function $P:[n] \rightarrow \{0,1,2,\ldots\}$ with $P(1) = P(n) = 0$ and $P(i+1) - P(i) \in S$ where $S = \{-1,1\}$. If we use the same definition except change $S$ to $\{-1,0,1\}$ ...
1
vote
3answers
25 views

A formula for a number of combinations

Say that you are selecting three numbers in the range $[1,n]$. What formula easily determines the number of combinations where one of the possible numbers (n for example) is selected exactly once? ...
1
vote
4answers
50 views

How many valuations of these literals satisfy this expression?

considering all the possible valuations of literals A, B, C, D, E, F, G and H (256 valuations in total), how would you go about finding how many of these valuations satisfy this expression: $$ ...
2
votes
1answer
24 views

Arranging books into more piles

Some books are arranged into $n$ piles. They're then rearranged into $n+k$ piles, where $k>0$. Show that at least $k+1$ books end up in a smaller pile than before. An induction on $k$ might be ...
4
votes
1answer
140 views

$n$ balls are thrown randomly into $k$ bins - how many are empty?

A large number of variants of this question were already asked here, including these - one, two, which are close, but none seem to answer my question. Assume that $n$ balls are thrown randomly and ...
15
votes
5answers
1k views

Puzzle of gold coins in the bag

At the end of Probability class, our professor gave us the following puzzle: There are 100 bags each with 100 coins, but only one of these bags has gold coins in it. The gold coin has weight of ...
5
votes
1answer
183 views

Closed-form formula for the $n^{\rm th}$ term of ${1,1,1,1,\ldots, 1}, {2,2,2,2,\ldots, 2},\ldots, {k-1, k-1}, k.$

Let $k$ be a positive integer. Consider a finite sequence $L_k(n)$ given by $$\underbrace{1,1,1,1,\ldots, 1}_{k\text{ terms}}, \underbrace{2,2,2,2,\ldots, 2}_{k-1\text{ terms}},\ldots, ...
5
votes
4answers
447 views

N choose k choose j

The Android mobile game "Pocket Tanks" has 295 unique weapons. For each match, 20 weapons are inserted into a list. Of those 20, players alternately draw weapons until all are exhausted, leaving each ...