For 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 (4)

0
votes
1answer
244 views

Combinatorics Problem - Clients using two seperate services

A financial group offers personal insurance and stock trading brokerage services. In total 10,000 people use their services. The group has 7,000 clients who use the insurance service and 5,000 who use ...
0
votes
1answer
30 views

Delannoy Paths and Pell Sequence Relation

I have the Pell sequence $a_n = 2a_{n-1} + a_{n-2}$ for $n \geq 2$ and $a_0 = 1, a_1=2$. I am trying to employ counting logic from Delannoy paths to show that $a_n = \sum\frac{(i+j+k)!}{i!j!k!}$ for ...
0
votes
1answer
149 views

Logic & Reasoning Question

At a track meet, every group of $n$ participants shares exactly one common friend. Suppose runner $P$ has the largest number of friends. Determine how many friends $P$ has. Assume for this question: ...
2
votes
1answer
124 views

Number of necklaces of 16 beads with 8 red beads, 4 green beads and 4 yellow beads

The question is as stated in the title up to symmetries of $D_{16}$. I know this has to do with the following two formulas: If $G=D_{16}$ is the group acting on the set $S$ of different necklaces, ...
0
votes
1answer
72 views

Discrete mathematics, sets, increasing functions

I have this assignment where I'm really lost and not sure how to solve. The assignment follows: We have two sets, $A = \{1,2,3,4,5,6,7\}$ and $X=\{a,b,c,d,e,f\}$. We say that a function $F$ is ...
0
votes
1answer
45 views

How many different games are there in bridge?

I know that there are ${52 \choose 13}$ hands. I was thinking maybe it was ${52 \choose 1} {52 \choose 39} {52 \choose 26} {52 \choose 13}$.
1
vote
0answers
38 views

finding exponential generating function by recursion in order to find the formal power series

If i define the number of permutation on n objects with order that divides 2 i get the recursion: a(n+2)=a(n+1)+(n+1)*a(n). then i can get the exponential generating function i(x)=sum(a(n)/n!*x^n)=...
4
votes
4answers
58 views

binomials product alternating sum calculation

I need to somehow prove that $\sum\limits_{k = 0}^{n - 1} {n \choose k} {3 n - k - 1 \choose 2 n - k}(-1)^k = (-1)^{n + 1} {2 n - 1 \choose n}$. I didn't manage to do it using induction or any ...
1
vote
0answers
32 views

How to find the ordinary generating function of a sequence from its exponential generating function?

Let $a$ and $b$ be positive constants. Suppose that $e^{at^2 + bt} = \sum_{k = 0}^\infty c_k t^k / k!$ is the exponential generating function of a sequence $\{c_k = c_k(a, b)\}$. How does one compute ...
0
votes
0answers
118 views

Cyclic shift in size K of a permutatoin P.

I am stucked in this question,can anyone please help me out.P is a permutation of integers 1, 2,... N. We want to change it a little. To do this, we choose an integer K that satisfies an inequality 2 ≤...
1
vote
0answers
47 views

Solution of $Connect4^{TM}$

It says here that Connect4 can be won by Player $1$ if their first counter goes in the middle column $4$, a draw if they play in columns $3$ or $5$, and Player $1$ loses everywhere else. As far as I ...
-1
votes
1answer
57 views

The probability that people select identical balls: two-person case is simple, but more-than-2-person case is complicated.

There are $n$ distinct balls. There are $p$ people, and the $i$th person selects $q_i$ distinct balls from these $n$ distinct balls. The question is: what is the probability that $q_0$ balls are ...
1
vote
1answer
40 views

Sum with binomial coefficients

How to find the sum $\sum_{k=1}^{m} k\binom{n}{k} \binom{n}{m-k}$? I also would be glad to know the generating function $\sum_{k=0}^{m} \binom{n}{k} \binom{n}{m-k}x^k$. Thank you.
1
vote
1answer
55 views

Number of permutations of $n$ objects with order 3 or 4

I am trying to see how I can find the number of permutations pi - lets say $a(n)$ - of $n$ objects with pi^3=id or pi^4=id. for example - $a(4)=24$, $a(5)=76$, $a(6)=336$. Is it something that can be ...
4
votes
1answer
66 views

Find number of integer solutions of linear equation

We're given an equation. $$ x_1 + x_2 + x_3 + x_4 + x_5 =21 $$ $$x_i \ge 0$$ aditionnal conditions are: $$ 0\le x_1 \le 3$$ $$ 1 \le x_2 \le4$$ $$ 15 \le x_3$$ Task is to find all integer solutions to ...
0
votes
1answer
27 views

Mapping the Number of Functions

I have read here how to figure out the number of functions between two sets A and B. But how do I figure the number of ways a function can be expressed within a another function. For example: (Let's ...
1
vote
0answers
60 views

Unique unclosed paths on torus grid

Consider a grid of points in the shape of torus with in my case $n=16$ points around the toroidal direction and $m=7$ points around the poloidal direction. Now draw a line by starting at any grid ...
2
votes
2answers
65 views

The number of ways to fill a 3 by 3 grid

I am currently studying the problem of combination. And when I am doing an exercise, I saw the following question: There is a 3 x 3 grid, and for each cells in the grid, two players take turn to fill ...
1
vote
0answers
57 views

Different Possible Combinations from Different Sets

I have 4 different sets A={a,b} B={c,d} C={e,f,g,h} D={h,i} I want to find the sum of distinct 2,3,4 letter combinations. Two letters cannot be chosen from the same set. (i.e) For a 3 letter ...
2
votes
1answer
44 views

Gaussian binomial coeffcient

Let the Gaussian Binomial Coefficient be defined for a prime $q$ as \begin{equation}\binom{N}{l}_{q}:=\prod_{i=0}^{l-1} \frac{q^{N-i}-1}{q^{l-i}-1}\end{equation} Now I want to show that, for $D>2$...
0
votes
2answers
50 views

Combinatorics theory question

Anyone know how to do this? In real life, if a person A is a friend of a person B then B is a friend of A. Let now S be the set of students in our department. Prove that there are at least two ...
1
vote
2answers
44 views

A combinatoric/probability puzzle

A horse race has four horses A, B, C and D. The probabilities for each horse to finish first or second are P(A)=80%, P(B)=60%, P(C)=40% and P(D)=20%. The probabilities add up to 200% because one ...
1
vote
1answer
33 views

Will removing the return leg from a traveling salesman problem ever change the results?

In a typical traveling salesman problem one starts at an origin point, visits a number of points once, then returns to the origin point in the most efficient way possible. Are there any scenarios in ...
2
votes
2answers
95 views

Generating functions for finding the coefficients

I am new to the field of combinatorics and I recently came across a problem where it was asked to find the number of integer solutions to ${c_1 + c_2 + c_3 + c_4=20 }$ where ${c_i\ge 0}$ for all ${1\...
0
votes
2answers
34 views

Probability of multiple dice rolls with constraints

I am having problems understanding how to tackle part b of the following question. A fair die is rolled three times. What is the probability that A) her second and third rolls are both larger ...
1
vote
0answers
33 views

Setting two variables equal in a multivariable holonomic function

If $f(x,y)$ is a holonomic (a.k.a. $D$-finite: https://en.wikipedia.org/wiki/Holonomic_function) function of two complex (or real) variables, is $g(x)=f(x,x)$ also holonomic?
0
votes
2answers
37 views

Probability for getting -1 in a game of rolling die

In a game, a fair die is rolled. If the result is 1 or 2, you can get 2 points. If the result is 3 or 4, you get -1 points. If the result is 5 or 6, you get 0 points. Now you can roll the die for 6 ...
0
votes
1answer
113 views

Applications of combinations with repetition

I am having problems understanding how to distinguish some combinatorial questions (specifically question 2 below). What distinguishes these two types of questions? In question 1, I can see that ...
3
votes
1answer
179 views

Number of partitions of a set into subsets of cardinality $k$.

I suppose that this question has already been asked, but I couldn't find it. Suppose we have a set $A$ with $nk$ elements. How many partitions of this set into sets of k elements are there?. For $n=k=...
3
votes
0answers
114 views

Combinatorial problem about splitting a finite set of real numbers

Given a finite set $X$ of real numbers greater than one. I'm looking for disjoint sets $A,B$ such that $X=A\cup B$ and such that $$\prod_{x\in A}x\leq\prod_{x\in B}x\,.$$ Especially am I interested ...
1
vote
3answers
36 views

Newton formula with out using induction

Is there a way to show that $$(a+b)^n=\sum_{k=0}^n \binom{n}{k}a^kb^{n-k}$$ where $a,b$ are positif integer with out using induction ?
3
votes
0answers
94 views

Class of all graphs with invertible adjacency matrices

This question is a generalization of the question asked here. From the answers of the questions, I can list four classes of graphs which have invertible adjacency matrices. The class of graphs $...
4
votes
0answers
139 views

Parity of a Permutation and Shifting

Given a permutation $P$ of $[1,2,...,n]$ and a positive integer $t\le n$. An operation is defined as shifting any $t$ consecutive elements of $P$ cyclically to the right by one index. For example: ...
1
vote
1answer
38 views

Problem of color painting

Each of $6$ points in space is connected to the other $5$ points by line segments.Each segment thus formed is colored greed or purple.Show that it is impossible to color all the segments without ...
3
votes
2answers
91 views

Combinatorial interpretation of convergent series

Given a series $$ \sum_{n=0}^\infty c_n x^n$$ that converges to $$ {1\over (1-x-x^{17}+x^{18})}$$ I am asked to give a combinatorical interpretation of $c_{10}$, more specifically in regards to a ...
6
votes
2answers
88 views

Rank of a matrix of binomial coefficients

This question arose as a side computation on error correcting codes. Let $k$, $r$ be positive integers such that $2k-1 \leqslant r$ and let $p$ a prime number such that $r < p$. I would like to ...
0
votes
1answer
43 views

find recurrence relation such that you have n digit sequence of $1$'s and $2$'s such that you have at least one instance of consecutive 2's [duplicate]

I let $a_n$ be the different sequences with $n$ digits such that there is at least one instance of consecutive $2$'s. This is what I did, if I place a a $1$ first, I have $n-1$ digits left and by ...
0
votes
2answers
130 views

Lottery payout with organizer margin.

Assume we have a lottery with payouts like this $(1,2,3,4,5,25,30,100)$ So you buy a ticket and you can win a pot which will multiply your ticket price by the numbers written ahead. The organizer ...
1
vote
1answer
31 views

Choose unique numbers from different sets

Suppose that there are n, possibly equal, non-empty sets. The problem is concerning choosing unique n numbers such that first ...
1
vote
1answer
45 views

The number of 3-digit numbers formed using the digits in set $S=\left\{0,1,2,3,4,5\right\}$,so that the digits either increase or decrease

The number of 3-digit numbers formed using the digits in set $S=\left\{0,1,2,3,4,5\right\}$,so that the digits either increase or decrease,is $(A)24\hspace{1cm}(B)30\hspace{1cm}(C)45\hspace{1cm}(D)56$ ...
0
votes
2answers
64 views

Number of ways of scoring a total of 20 runs in one over of six balls

A batsman can score $0,2,3$ or $4$ runs for each ball he receives.If $N$ is the number of ways of scoring a total of 20 runs in one over of six balls.Then find $N$. Different options of scoring $20$...
0
votes
3answers
115 views

Addresses in decimal,binary,octal and hexadecimal

One of the first minicomputers, the PDP-8 had a word size of 12 bits. (Recall the word size of a computer refers to the number of bits used to encode addresses.) what was the last address in this ...
2
votes
3answers
604 views

How many 3 digit odd numbers greater than 600 can be formed using the digits(2,3,4,5,6 and 7)? [closed]

In my worksheet the answer is 20 but i keep getting a different answer
0
votes
2answers
56 views

Number of ways to put $n$ red cards and $k$ black cards into $4$ distinct jars so that every jar has a card.

So if we define two functions $f_1 [n]\rightarrow [4]$ and $f_2[k]\rightarrow [4]$, in order to do this problem we need for the functions to be onto. This is simple enough, right? If $f_1$ is onto ...
0
votes
1answer
79 views

In how many ways can we select $x$ distinct candies from a collection of $n$ candies of distinct types? [closed]

Suppose we have k distinct types of jars. Lets name these jars as jar1 , jar2 , jar3....jark Now each jar have some candies. A jar will have same type of candies. Moreover no two jars have same ...
1
vote
0answers
21 views

Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
0
votes
1answer
36 views

Optimization of shopping list by condition

I am a computer science student that is struggling with a problem of mathematical nature. Thus far I have only studied calculus, discrete mathematics and linear algebra, but cannot figure out how to ...
3
votes
1answer
85 views

Ants moving on a grid

I got asked this as a programming interview question so the "correct" solution is via simulation, but I'm curious about the existence of an analytic solution. Two ants start in opposing corners of ...
7
votes
2answers
208 views

Coloring the windmill

A windmill has $5$ wings and each of these is symmetrically connected to the axis and consists of two parts. If on the wings of the windmill $4$ parts are colored black, $3$ parts are colored red, ...
1
vote
1answer
21 views

Permutation in which the $A's$ appear together in a block of $4$ letters or the $B's$ appear together in a block of $3$ letters

The number of permutation of all the letters $AAAABBBC$ in which the $A's$ appear together in a block of $4$ letters or the $B's$ appear together in a block of $3$ letters is : $(A)44\hspace{1cm}(B)50\...